// Definition for a Node.
class Node {
public:
  int val;
  Node *prev;
  Node *next;
  Node *child;
};

struct NodePack {
  Node *Head;
  Node *Tail;
};

class Solution {
public:
  NodePack Proc(Node *Now) {
    Node *p = Now;
    Node *q = nullptr;
    while (p != nullptr) {
      if (p->child != nullptr) {
        NodePack temp = Proc(p->child);
        temp.Tail->next = p->next;
        if (p->next != nullptr) {
          p->next->prev = temp.Tail;
        }
        p->next = temp.Head;
        temp.Head->prev = p;
        p->child = nullptr;
      }
      q = p;
      p = p->next;
    }
    return {Now, q};
  }
  Node *flatten(Node *head) {
    NodePack temp = Proc(head);
    return temp.Head;
  }
};
